from typing import List


class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n1 = len(nums)

        nums = sorted(set(nums))

        n2 = len(nums)

        # 初始化滑动窗口
        left = 0
        right = 0
        same = 0
        while right + 1 < n2 and nums[right + 1] < nums[left] + n1:
            right += 1

        # 当前ans为不需要修改的数量
        ans = right - left + 1 - same

        while left + 1 < n2:
            left += 1
            while right + 1 < n2 and nums[right + 1] < nums[left] + n1:
                right += 1
            ans = max(ans, right - left + 1 - same)

        return n1 - ans


if __name__ == "__main__":
    print(Solution().minOperations(nums=[4, 2, 5, 3]))  # 0
    print(Solution().minOperations(nums=[1, 2, 3, 5, 6]))  # 1
    print(Solution().minOperations(nums=[1, 10, 100, 1000]))  # 3

    # 测试用例25/62
    print(Solution().minOperations(nums=[8, 5, 9, 9, 8, 4]))  # 2
